package 刷题10月.笔试题;
import java.util.*;
//合并数组中的topk问题富途
public class Main1 {
    public static class HeapNode{
        public int row;
        public int col;
        public int value;

        public HeapNode(int row, int col, int value) {
            this.row = row;
            this.col = col;
            this.value = value;
        }
    }


        /**
         * find topK in two sorted array
         * @param arr1 int整型一维数组 the array1
         * @param arr2 int整型一维数组 the array2
         * @param k int整型 the k
         * @return int整型一维数组
         */
        public int[] findTopKinTwoSortedArray (int[] arr1, int[] arr2, int k) {
            // write code here
            if(arr1==null||arr2==null||k<1){
                return null;
            }
            k=Math.min(k,arr1.length*arr2.length);
            int res[]=new int[k];
            int resIndex=0;
            PriorityQueue<HeapNode> maxHeap=new PriorityQueue<>((N1,N2)->N2.value-N1.value);
            HashSet<String> set=new HashSet<>();
            int i1=arr1.length-1;
            int i2=arr2.length-1;
            maxHeap.add(new HeapNode(i1,i2,arr1[i1]+arr2[i2]));
            set.add(i1+"_"+i2);
            while(resIndex!=k){

                HeapNode current=maxHeap.poll();
                res[resIndex++]=current.value;
                i1=current.row;
                i2=current.col;
                if(i1-1>=0&&!set.contains(i1-1+"_"+i2)){
                    set.add(i1-1+"_"+i2);
                    maxHeap.add(new HeapNode(i1-1,i2,arr1[i1-1]+arr2[i2]));
                }
                if(i2-1>=0&&!set.contains(i1+"_"+(i2-1))){
                    set.add(i1+"_"+(i2-1));
                    maxHeap.add(new HeapNode(i1,i2-1,arr1[i1]+arr2[i2-1]));
                }
            }
            return res;
        }



}
